home *** CD-ROM | disk | FTP | other *** search
/ Aminet 21 / Aminet 21 (1997)(GTI - Schatztruhe)[!][Oct 1997].iso / Aminet / gfx / show / gs_src_gs.lha / gs5.03 / gxdither.c < prev    next >
C/C++ Source or Header  |  1996-05-18  |  17KB  |  479 lines
  1. /* Copyright (C) 1989, 1995, 1996 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* gxdither.c */
  20. #include "gx.h"
  21. #include "gsstruct.h"
  22. #include "gsdcolor.h"
  23. #include "gxdevice.h"
  24. #include "gxlum.h"
  25. #include "gxcmap.h"
  26. #include "gxdither.h"
  27. #include "gzht.h"
  28.  
  29. /*
  30.  * The procedures in this file use halftoning (if necessary)
  31.  * to implement a given device color that has already gone through
  32.  * the transfer function.  There are two major cases: gray and color.
  33.  * Gray halftoning always uses a binary screen.  Color halftoning
  34.  * uses either a fast algorithm with a binary screen that produces
  35.  * relatively poor approximations, or a very slow algorithm with a
  36.  * general colored screen (or screens) that faithfully implements
  37.  * the Adobe specifications.
  38.  */
  39.  
  40. /* Tables for fast computation of fractional color levels. */
  41. /* We have to put the table before any uses of it because of a bug */
  42. /* in the VAX C compiler. */
  43. /* We have to split up the definition of the table itself because of a bug */
  44. /*  in the IBM AIX 3.2 C compiler. */
  45. private const gx_color_value
  46.   q0[] = { 0 };
  47. private const gx_color_value
  48.   q1[] = { 0, frac_color_(1,1) };
  49. private const gx_color_value
  50.   q2[] = { 0, frac_color_(1,2), frac_color_(2,2) };
  51. private const gx_color_value
  52.   q3[] = { 0, frac_color_(1,3), frac_color_(2,3), frac_color_(3,3) };
  53. private const gx_color_value
  54.   q4[] = { 0, frac_color_(1,4), frac_color_(2,4), frac_color_(3,4), frac_color_(4,4) };
  55. private const gx_color_value
  56.   q5[] = { 0, frac_color_(1,5), frac_color_(2,5), frac_color_(3,5), frac_color_(4,5), frac_color_(5,5) };
  57. private const gx_color_value
  58.   q6[] = { 0, frac_color_(1,6), frac_color_(2,6), frac_color_(3,6), frac_color_(4,6), frac_color_(5,6), frac_color_(6,6) };
  59. private const gx_color_value
  60.   q7[] = { 0, frac_color_(1,7), frac_color_(2,7), frac_color_(3,7), frac_color_(4,7), frac_color_(5,7), frac_color_(6,7), frac_color_(7,7) };
  61. /* We export fc_color_quo for the fractional_color macro in gzht.h. */
  62. const gx_color_value _ds *fc_color_quo[8] =
  63.  { q0, q1, q2, q3, q4, q5, q6, q7 };
  64.  
  65. /* Render a gray, possibly by halftoning. */
  66. int
  67. gx_render_device_gray(frac gray, gx_color_value alpha, gx_device_color *pdevc,
  68.   gx_device *dev, const gx_device_halftone *pdht,
  69.   const gs_int_point *ht_phase)
  70. {    bool cmyk = dev->color_info.num_components == 4;
  71.  
  72. /* Make a special check for black and white. */
  73.     if ( alpha == gx_max_color_value )
  74.     {    gx_color_value lum;
  75.         switch ( gray )
  76.           {
  77.           case frac_0:
  78.             lum = 0;
  79.             goto bw;
  80.           case frac_1:
  81.             lum = gx_max_color_value;
  82. bw:            color_set_pure(pdevc,
  83.                        (cmyk ? 
  84.                     gx_map_cmyk_color(dev, 0, 0, 0,
  85.                         gx_max_color_value - lum) :
  86.                     gx_map_rgb_color(dev, lum, lum, lum)));
  87.             return 0;
  88.           default:
  89.             ;
  90.           }
  91.     }
  92.  
  93. /* get a few handy values */
  94.     {    uint max_value = dev->color_info.dither_grays - 1;
  95.         unsigned long hsize = (unsigned)pdht->order.num_levels;
  96.         unsigned long nshades = hsize * max_value + 1;
  97.         unsigned long lx = (nshades * gray) / (frac_1_long + 1);
  98.         uint v = lx / hsize;
  99.         gx_color_value lum = fractional_color(v, max_value);
  100.         gx_color_index color1;
  101.         int level = lx % hsize;
  102.         /* The following should be a conditional expression, */
  103.         /* but the DECStation 3100 Ultrix 4.3 compiler */
  104.         /* generates bad code for it. */
  105. #define set_color_lum(col, lum)\
  106.   if ( cmyk )\
  107.     col = gx_map_cmyk_color(dev, 0, 0, 0,\
  108.                    gx_max_color_value - lum);\
  109.   else if ( alpha == gx_max_color_value )\
  110.     col = gx_map_rgb_color(dev, lum, lum, lum);\
  111.   else\
  112.     col = gx_map_rgb_alpha_color(dev, lum, lum, lum, alpha)
  113.         set_color_lum(color1, lum);
  114.         if_debug5('c', "[c]gray=0x%x --> (%d+%d/%lu)/%d\n",
  115.               (unsigned)gray, v, level, hsize, max_value + 1);
  116.         if ( level == 0 )
  117.         {    /* Close enough to a pure color, */
  118.             /* no dithering needed. */
  119.             color_set_pure(pdevc, color1);
  120.             return 0;
  121.         }
  122.         else
  123.         {    gx_color_index color2;
  124.             v++;
  125.             lum = fractional_color(v, max_value);
  126.             set_color_lum(color2, lum);
  127.             color_set_binary_halftone(pdevc, pdht,
  128.                           color1, color2, level);
  129.             color_set_phase_mod(pdevc, ht_phase->x, ht_phase->y,
  130.                         pdht->order.width,
  131.                         pdht->order.full_height);
  132.             return 1;
  133.         }
  134.     }
  135. }
  136.  
  137. /* 
  138.  *    Color dithering for Ghostscript.  The underlying device imaging model
  139.  *    supports dithering between two colors to generate intermediate shades.
  140.  *    
  141.  *    If the device has high quality colors (at least 32 values
  142.  *    per axis), we ask it to map the color directly.
  143.  *
  144.  *    Otherwise, things are a bit more complicated.  If the device 
  145.  *     supports N shades of each R, G and B independently, there are a total 
  146.  *    of N*N*N colors.  These colors form a 3-D grid in a cubical color 
  147.  *    space.  The following dithering technique works by locating the 
  148.  *    color we want in this 3-D color grid and finding the eight colors 
  149.  *     that surround it.  In the case of dithering into 8 colors with 1 
  150.  *    bit for each red, green and blue, these eight colors will always 
  151.  *    be the same.
  152.  *
  153.  *    Now we consider all possible diagonal paths between the eight colors
  154.  *    and chose the path that runs closest to our desired color in 3-D
  155.  *    color space.  There are 28 such paths.  Then we find the position
  156.  *    on the path that is closest to our color.
  157.  *
  158.  *    The search is made faster by always reflecting our color into
  159.  *    the bottom octant of the cube and comparing it to 7 paths.
  160.  *    After the best path and the best position on that path are found,
  161.  *    the results are reflected back into the original color space.
  162.  *
  163.  *    NOTE: This code has been tested for B/W and Color imaging with
  164.  *    1, 2, 3 and 8 bits per component.
  165.  *
  166.  *    --- original code by Paul Haeberli @ Silicon Graphics - 1990
  167.  *    --- extensively revised by L. Peter Deutsch, Aladdin Enterprises
  168.  *
  169.  *    lpd 3/14/94: added support for CMYK.
  170.  */
  171.  
  172. /*
  173.  * The weights are arbitrary, as long as their ratios are correct
  174.  * and they will fit into the difference between a ulong and a frac
  175.  * with room to spare.  By making WEIGHT1 and WEIGHT4 powers of 2,
  176.  * we can turn some multiplies into shifts.
  177.  */
  178. #define WNUM 128000
  179. #define    WEIGHT1        (ulong)(WNUM/1000)    /* 1.0            */
  180. #define    WEIGHT2        (ulong)(WNUM/1414)    /* 1/sqrt(2.0)        */
  181. #define    WEIGHT3        (ulong)(WNUM/1732)    /* 1/sqrt(3.0)        */
  182. #define WEIGHT4        (ulong)(WNUM/2000)    /* 1/sqrt(4.0)        */
  183.  
  184. #define    DIAG_R        (0x1)
  185. #define    DIAG_G        (0x2)
  186. #define    DIAG_B        (0x4)
  187. #define DIAG_W        (0x8)
  188. #define    DIAG_RG        (0x3)
  189. #define    DIAG_GB        (0x6)
  190. #define    DIAG_BR        (0x5)
  191. #define    DIAG_RGB    (0x7)
  192. #define DIAG_RGBW    (0xf)
  193.  
  194. /* What should we do about the W/K component?  For the moment, */
  195. /* we ignore it in the luminance computation. */
  196. #define lum_white_weight 0
  197. private const unsigned short lum_w[16] = {
  198.     (0*lum_blue_weight+0*lum_green_weight+0*lum_red_weight+0*lum_white_weight),
  199.     (0*lum_blue_weight+0*lum_green_weight+1*lum_red_weight+0*lum_white_weight),
  200.     (0*lum_blue_weight+1*lum_green_weight+0*lum_red_weight+0*lum_white_weight),
  201.     (0*lum_blue_weight+1*lum_green_weight+1*lum_red_weight+0*lum_white_weight),
  202.     (1*lum_blue_weight+0*lum_green_weight+0*lum_red_weight+0*lum_white_weight),
  203.     (1*lum_blue_weight+0*lum_green_weight+1*lum_red_weight+0*lum_white_weight),
  204.     (1*lum_blue_weight+1*lum_green_weight+0*lum_red_weight+0*lum_white_weight),
  205.     (1*lum_blue_weight+1*lum_green_weight+1*lum_red_weight+0*lum_white_weight),
  206.     (0*lum_blue_weight+0*lum_green_weight+0*lum_red_weight+1*lum_white_weight),
  207.     (0*lum_blue_weight+0*lum_green_weight+1*lum_red_weight+1*lum_white_weight),
  208.     (0*lum_blue_weight+1*lum_green_weight+0*lum_red_weight+1*lum_white_weight),
  209.     (0*lum_blue_weight+1*lum_green_weight+1*lum_red_weight+1*lum_white_weight),
  210.     (1*lum_blue_weight+0*lum_green_weight+0*lum_red_weight+1*lum_white_weight),
  211.     (1*lum_blue_weight+0*lum_green_weight+1*lum_red_weight+1*lum_white_weight),
  212.     (1*lum_blue_weight+1*lum_green_weight+0*lum_red_weight+1*lum_white_weight),
  213.     (1*lum_blue_weight+1*lum_green_weight+1*lum_red_weight+1*lum_white_weight)
  214. };
  215.  
  216. /* Render RGB or CMYK, possibly by halftoning. */
  217. /* If we are rendering RGB, white is ignored. */
  218. /* If we are rendering CMYK, red/green/blue/white are actually */
  219. /* cyan/magenta/yellow/black. */
  220. int
  221. gx_render_device_color(frac red, frac green, frac blue, frac white, bool cmyk,
  222.   gx_color_value alpha, gx_device_color *pdevc, gx_device *dev,
  223.   const gx_device_halftone *pdht, const gs_int_point *ht_phase)
  224. {    uint max_value = dev->color_info.dither_colors - 1;
  225.     uint num_levels = pdht->order.num_levels;
  226.     frac rem_r, rem_g, rem_b, rem_w;
  227.     uint r, g, b, w;
  228.     gx_color_value vr, vg, vb, vw;
  229. #define map_color_rgb()\
  230.   (alpha == gx_max_color_value ?\
  231.    gx_map_rgb_color(dev, vr, vg, vb) :\
  232.    gx_map_rgb_alpha_color(dev, vr, vg, vb, alpha))
  233. #define map_color_cmyk()\
  234.   gx_map_cmyk_color(dev, vr, vg, vb, vw)
  235. #define map_color()\
  236.   (cmyk ? map_color_cmyk() : map_color_rgb())
  237.  
  238.     /* Compute the quotient and remainder of each color component */
  239.     /* with the actual number of available colors. */
  240.     switch ( max_value )
  241.     {
  242.     case 1:            /* 8 or 16 colors */
  243.         if ( red == frac_1 ) rem_r = 0, r = 1;
  244.         else rem_r = red, r = 0;
  245.         if ( green == frac_1 ) rem_g = 0, g = 1;
  246.         else rem_g = green, g = 0;
  247.         if ( blue == frac_1 ) rem_b = 0, b = 1;
  248.         else rem_b = blue, b = 0;
  249.         if ( white == frac_1 ) rem_w = 0, w = 1;
  250.         else rem_w = white, w = 0;
  251.         break;
  252.     default:
  253.        {    ulong want_r, want_g, want_b, want_w;
  254.         want_r = (ulong)max_value * red;
  255.         r = frac_1_quo(want_r);
  256.         rem_r = frac_1_rem(want_r, r);
  257.         want_g = (ulong)max_value * green;
  258.         g = frac_1_quo(want_g);
  259.         rem_g = frac_1_rem(want_g, g);
  260.         want_b = (ulong)max_value * blue;
  261.         b = frac_1_quo(want_b);
  262.         rem_b = frac_1_rem(want_b, b);
  263.         want_w = (ulong)max_value * white;
  264.         w = frac_1_quo(want_w);
  265.         rem_w = frac_1_rem(want_w, w);
  266.        }
  267.     }
  268.  
  269.     /* Check for no dithering required */
  270.     if ( !(rem_r | rem_g | rem_b | rem_w) )
  271.     {    vr = fractional_color(r, max_value);
  272.         vg = fractional_color(g, max_value);
  273.         vb = fractional_color(b, max_value);
  274.         vw = fractional_color(w, max_value);
  275.         color_set_pure(pdevc, map_color());
  276.         return 0;
  277.     }
  278.  
  279.     if_debug12('c', "[c]rgbw=0x%x,0x%x,0x%x,0x%x -->\n   %x+0x%x,%x+0x%x,%x+0x%x,%x+0x%x -->\n",
  280.           (unsigned)red, (unsigned)green, (unsigned)blue, (unsigned)white,
  281.           (unsigned)r, (unsigned)rem_r, (unsigned)g, (unsigned)rem_g,
  282.           (unsigned)b, (unsigned)rem_b, (unsigned)w, (unsigned)rem_w);
  283.  
  284.     /* Dithering is required.  Choose between two algorithms. */
  285.       
  286.     if ( pdht->components != 0 && dev->color_info.depth >= 4 )
  287.     {    /* Someone went to the trouble of setting different */
  288.         /* screens for the different components. */
  289.         /* Use the slow, general colored halftone algorithm. */
  290. #define rgb_rem(rem_v, i)\
  291.   (rem_v * (ulong)(pdht->components[pdht->color_indices[i]].corder.num_levels) / frac_1)
  292.         uint lr = rgb_rem(rem_r, 0), lg = rgb_rem(rem_g, 1),
  293.           lb = rgb_rem(rem_b, 2);
  294.         if ( cmyk )
  295.           color_set_cmyk_halftone(pdevc, pdht, r, lr, g, lg, b, lb,
  296.                       w, rgb_rem(rem_w, 3));
  297.         else
  298.           color_set_rgb_halftone(pdevc, pdht, r, lr, g, lg, b, lb, alpha);
  299.         color_set_phase_mod(pdevc, ht_phase->x, ht_phase->y,
  300.                     pdht->lcm_width, pdht->lcm_height);
  301. #undef rgb_rem
  302.         return 1;
  303.     }
  304.  
  305.     /* Fast, approximate binary halftone algorithm. */
  306.     
  307.   {    ulong hsize = num_levels;
  308.     int adjust_r, adjust_b, adjust_g, adjust_w;
  309.     gx_color_index color1;
  310.     frac amax, amin;
  311.     ulong fmax, cmax;
  312.     int axisc, facec, cubec, diagc;
  313.     unsigned short lum_invert;
  314.     ulong dot1, dot2, dot3, dot4;
  315.     int level;
  316.     int code;
  317.  
  318. /* Flip the remainder color into the 0, 0, 0 octant. */
  319.     lum_invert = 0;
  320. #define half (frac_1/2)
  321.     if ( rem_r > half )
  322.         rem_r = frac_1 - rem_r,
  323.           adjust_r = -1, r++, lum_invert += lum_red_weight * 2;
  324.     else
  325.         adjust_r = 1;
  326.     if ( rem_g > half )
  327.         rem_g = frac_1 - rem_g,
  328.           adjust_g = -1, g++, lum_invert += lum_green_weight * 2;
  329.     else
  330.         adjust_g = 1;
  331.     if ( rem_b > half )
  332.         rem_b = frac_1 - rem_b,
  333.           adjust_b = -1, b++, lum_invert += lum_blue_weight * 2;
  334.     else
  335.         adjust_b = 1;
  336.     vr = fractional_color(r, max_value);
  337.     vg = fractional_color(g, max_value);
  338.     vb = fractional_color(b, max_value);
  339.     if ( cmyk )
  340.       {    if ( rem_w > half )
  341.           rem_w = frac_1 - rem_w,
  342.             adjust_w = -1, b++, lum_invert += lum_white_weight * 2;
  343.         else
  344.           adjust_w = 1;
  345.         vw = fractional_color(w, max_value);
  346.         color1 = map_color_cmyk();
  347.       }
  348.     else
  349.       color1 = map_color_rgb();
  350.  
  351. /* 
  352.  * Dot the color with each axis to find the best one of 15;
  353.  * find the color at the end of the axis chosen.
  354.  */
  355.     cmax = (ulong)rem_r+rem_g+rem_b;
  356.     dot4 = cmax + rem_w;
  357.     if ( rem_g > rem_r )
  358.       {    if ( rem_b > rem_g )
  359.           amax = rem_b, axisc = DIAG_B;
  360.         else
  361.           amax = rem_g, axisc = DIAG_G;
  362.         if ( rem_b > rem_r )
  363.           amin = rem_r, fmax = (ulong)rem_g+rem_b, facec = DIAG_GB;
  364.         else
  365.           amin = rem_b, fmax = (ulong)rem_r+rem_g, facec = DIAG_RG;
  366.       }
  367.     else
  368.       {    if ( rem_b > rem_r )
  369.           amax = rem_b, axisc = DIAG_B;
  370.         else
  371.           amax = rem_r, axisc = DIAG_R;
  372.         if ( rem_b > rem_g )
  373.           amin = rem_g, fmax = (ulong)rem_b+rem_r, facec = DIAG_BR;
  374.         else
  375.           amin = rem_b, fmax = (ulong)rem_r+rem_g, facec = DIAG_RG;
  376.       }
  377.     if ( rem_w > amin )
  378.       {    cmax = fmax + rem_w, cubec = facec + DIAG_W;
  379.         if ( rem_w > amax )
  380.           fmax = (ulong)amax + rem_w, facec = axisc + DIAG_W,
  381.           amax = rem_w, axisc = DIAG_W;
  382.         else if ( rem_w > fmax - amax )
  383.           fmax = (ulong)amax + rem_w, facec = axisc + DIAG_W;
  384.       }
  385.     else
  386.         cubec = DIAG_RGB;
  387.  
  388.     dot1 = amax*WEIGHT1;
  389.     dot2 = fmax*WEIGHT2;
  390.     dot3 = cmax*WEIGHT3;
  391.     /*dot4 see above*/
  392. #define use_axis()\
  393.   diagc = axisc, level = (hsize * amax + (frac_1_long / 2)) / frac_1_long
  394. #define use_face()\
  395.   diagc = facec, level = (hsize * fmax + frac_1_long) / (2 * frac_1_long)
  396. #define use_cube()\
  397.   diagc = cubec, level = (hsize * cmax + (3 * frac_1_long / 2)) / (3 * frac_1_long)
  398. #define use_tesseract()\
  399.   diagc = DIAG_RGBW, level = (hsize * dot4 + (2 * frac_1_long)) / (4 * frac_1_long)
  400.     if ( dot1 > dot2 )
  401.       {    if ( dot3 > dot1 )
  402.           {    if ( dot4*WEIGHT4 > dot3 )
  403.               use_tesseract();
  404.             else
  405.               use_cube();
  406.           }
  407.         else
  408.           {    if ( dot4*WEIGHT4 > dot1 )
  409.               use_tesseract();
  410.             else
  411.               use_axis();
  412.           }
  413.       }
  414.     else
  415.       {    if ( dot3 > dot2 )
  416.           {    if ( dot4*WEIGHT4 > dot3 )
  417.               use_tesseract();
  418.             else
  419.               use_cube();
  420.           }
  421.         else
  422.           {    if ( dot4*WEIGHT4 > dot2 )
  423.               use_tesseract();
  424.             else
  425.               use_face();
  426.           }
  427.       };
  428.  
  429.     if_debug12('c', "   %x+0x%x,%x+0x%x,%x+0x%x,%x+0x%x; adjust=%d,%d,%d,%d\n",
  430.           (unsigned)r, (unsigned)rem_r, (unsigned)g, (unsigned)rem_g,
  431.           (unsigned)b, (unsigned)rem_b, (unsigned)w, (unsigned)rem_w,
  432.           adjust_r, adjust_g, adjust_b, adjust_w);
  433.  
  434.     if ( level == 0 )
  435.     {    color_set_pure(pdevc, color1);
  436.         code = 0;
  437.     }
  438.     else
  439.     {    gx_color_index color2;
  440. /* construct the second color, inverting back to original space if needed */
  441.         if (diagc & DIAG_R) r += adjust_r;
  442.         if (diagc & DIAG_G) g += adjust_g;
  443.         if (diagc & DIAG_B) b += adjust_b;
  444. /* get the second device color, sorting by luminance */
  445.         vr = fractional_color(r, max_value);
  446.         vg = fractional_color(g, max_value);
  447.         vb = fractional_color(b, max_value);
  448.         if ( cmyk )
  449.           { if (diagc & DIAG_W) w += adjust_w;
  450.             vw = fractional_color(w, max_value);
  451.             color2 = map_color_cmyk();
  452.           }
  453.         else
  454.           color2 = map_color_rgb();
  455.         if ( level == num_levels )
  456.           {    /* This can only happen through rounding.... */
  457.             color_set_pure(pdevc, color2);
  458.             code = 0;
  459.           }
  460.         else
  461.           {    if ( lum_w[diagc] < lum_invert )
  462.               color_set_binary_halftone(pdevc, pdht, color2, color1, hsize - level);
  463.             else
  464.               color_set_binary_halftone(pdevc, pdht, color1, color2, level);
  465.             color_set_phase_mod(pdevc, ht_phase->x, ht_phase->y,
  466.                         pdht->order.width,
  467.                         pdht->order.full_height);
  468.             code = 1;
  469.           }
  470.     }
  471.  
  472.     if_debug7('c', "[c]diagc=%d; colors=0x%lx,0x%lx; level=%d/%d; lum=%d,diag=%d\n",
  473.           diagc, (ulong)pdevc->colors.binary.color[0],
  474.           (ulong)pdevc->colors.binary.color[1],
  475.           level, (unsigned)hsize, lum_invert, lum_w[diagc]);
  476.     return code;
  477.   }
  478. }
  479.